from collections import defaultdict
from typing import List


class Solution:
    def ringGame(self, challenge: List[int]) -> int:
        # 最终结果一定大于最大位
        max_val = max(challenge)
        max_bit = max_val.bit_length()  # 最大位
        bit_val = 1 << (max_bit - 1)  # 最大位的值
        # print("最大值:", max_val, "最大位:", max_bit, "最大位的值:", bit_val)

        # ----- 将小于最大位的值的数合并 -----
        # 新数组：[当前值,当前左右合并小数之后的值]
        clear1 = []
        less_val = 0  # 当前两个大值之间间隔的小值的OR
        for num in challenge:
            if num < bit_val:
                less_val |= num
            else:
                if len(clear1) > 0:
                    clear1[-1][1] |= less_val
                if less_val > 0:
                    clear1.append([bit_val, bit_val | less_val])
                clear1.append([num, num | less_val])
                less_val = 0
        clear1[-1][1] |= less_val

        size = len(clear1)

        print("第1次整理结果:", clear1)

        # # ----- 尝试合并 -----
        # stack = []  # 单调栈
        # clear2 = []
        # for v2, m2 in clear1:
        #     if not stack or stack:
        #         stack.append([v2, m2])
        #         continue
        #     v1, m1 = clear2[-1]
        #     if m2 >= v1:  # 前面的可以合并后面的
        #         clear2[-1] =
        #     if v2 >= clear2[-1][0] and m2 >= clear2[-1][1]:
        #         clear2[-1][0] = min(clear2[-1][0], v2)
        #         clear2[-1][1] = max(clear2[-1][1], m2)
        #     else:
        #         clear2.append([v2, m2])
        # print("第2次整理结果:", clear2)

        # ----- 整理每一种情况的哈希值 -----
        hash_lst = defaultdict(list)
        for i, elem in enumerate(clear1):
            v0, m0 = elem
            hash_lst[v0].append(i)
        print("hash_lst:", hash_lst)

        # 二分查找
        hash_keys = sorted(hash_lst.keys())
        print("hash_keys:", hash_keys)

        left = 0
        right = len(hash_keys) - 1
        # print("二分边界:", left, right)

        while left < right:
            mid = (left + right) // 2

            # 尝试检查mid是否可能
            queue = []
            num = 0
            visited = [0] * size
            for i in hash_lst[hash_keys[mid]]:
                visited[i] = clear1[i][1]
                queue.append(i)
                num += 1
            while queue:
                i = queue.pop()
                l, r = i - 1, i + 1
                if l == -1:
                    l = size - 1
                if r == size:
                    r = 0

                if clear1[l][0] <= visited[i] and visited[l] == 0:
                    visited[l] = max(clear1[l][1], visited[i])
                    queue.append(i)
                    num += 1
                if clear1[r][0] <= visited[i] and visited[r] == 0:
                    visited[r] = max(clear1[r][1], visited[i])
                    queue.append(i)
                    num += 1

            print(mid, ":", num == size)

            if num == size:  # 成功遍历所有点，当前点符合（保证right符合）
                right = mid
            else:  # 当前点不符合
                left = mid + 1

        return hash_keys[right]


if __name__ == "__main__":
    print(Solution().ringGame(challenge=[5, 4, 6, 2, 7]))  # 4
    print(Solution().ringGame(challenge=[12, 7, 11, 3, 9]))  # 8
    print(Solution().ringGame(challenge=[1, 1, 1]))  # 1

    # 自制用例
    print(Solution().ringGame(challenge=[15, 6, 15, 1]))  # 15
    print(Solution().ringGame(challenge=[5, 7, 11, 13, 14, 15]))  # 8
    print(Solution().ringGame(challenge=[15, 11, 13, 15]))  # 11
